class countingDict extends Object {
  //use object as a dictionary
  incrementItem(key, addValue = 1) {
    // a*y*x --> a*x*y:
    key = new CalcString(key)
      .splitIntoArrayByFree("*", "mode2")
      .sort(mixedCompare)
      .join("*");
    if (this.hasOwnProperty(key)) {
      this[key] += addValue;
      if (Math.abs(this[key]) < ErrorVal) delete this[key];
    } else this[key] = addValue;
  }
  decrementItem(key) {
    key = new CalcString(key)
      .splitIntoArrayByFree("*", "mode2")
      .sort(mixedCompare)
      .join("*");
    if (this.hasOwnProperty(key)) {
      this[key]--;
      if (Math.abs(this[key]) < ErrorVal) {
        delete this[key];
        return true;
      } else {
        console.log("no this key: " + key);
        return false;
      }
    }
  }
}
class CalcString extends String {
  //strings with several functions
  constructor(str = "!") {
    super("!");
    this.str = str;
    this.strUpdated = true;
    this.parInfo = [];
    this.numerator = [];
    this.denominator = [];
    this.sign = 1;
    this.needReduce = false;
    this.dPart = this.sPart = ""; //digital part and symbol part
  }
  toString() {
    return this.str;
  }
  parenthesisAnalysis() {
    let left = 0;
    let right = 0;
    for (let i = 0; i < this.str.length; i++) {
      this.parInfo[i] = { left: null, right: null };
      this.parInfo[i].left = left;
      this.parInfo[i].right = right;
      if (this.str[i] == "(") left++;
      else if (this.str[i] == ")") right++;
    }
    this.strUpdated = false;
  }
  findFreeNdx(op) {
    if (this.strUpdated) {
      this.parInfo = [];
      this.parenthesisAnalysis();
    }
    op = op.replaceAll(/[-\/\\^$*+?.()|[\]{}]/g, "\\$&");
    let re = new RegExp("[" + op + "]", "g");
    let matched = this.str.toString().matchAll(re);
    let ndx = [];
    for (let i of matched)
      if (
        this.parInfo.length > 0 &&
        this.parInfo[i.index].left == this.parInfo[i.index].right
      )
        ndx.push(i.index);
    return ndx;
  }
  hasFree(op) {
    let ndx = this.findFreeNdx(op);
    return ndx.length && ndx.toString() != "0";
  }
  splitIntoArrayByFree(op, mode = "mode1") {
    //mode: 1:["-","a","+","b","*","c"]; 2: ["a","b","c"](with own sign); 3:["-a","+b","*c"]
    let arr = [];
    let ndx = [];
    if (op.includes("+") || op.includes("-"))
      if (this.str[0] != "-") this.str = "+" + this.str;
    ndx = this.findFreeNdx(op);
    if (ndx.length == 0) arr.push(new CalcString(this.str));
    else {
      if (ndx[0] == 0) {
        ndx.push(this.str.length);
        for (let i = 0; i < ndx.length - 1; i++) {
          arr.push(this.str.substring(ndx[i], ndx[i] + 1));
          arr.push(new CalcString(this.str.substring(ndx[i] + 1, ndx[i + 1])));
          if (arr[arr.length - 2] == "-") arr[arr.length - 1].sign = 0;
        }
      } else {
        //ndx[0]>0
        ndx.unshift(0);
        arr.push(new CalcString(this.str.substring(0, ndx[1])));
        ndx.push(this.str.length);
        for (let i = 1; i < ndx.length - 1; i++) {
          arr.push(this.str.substring(ndx[i], ndx[i] + 1));
          arr.push(new CalcString(this.str.substring(ndx[i] + 1, ndx[i + 1])));
          if (arr[arr.length - 2] == "-") arr[arr.length - 1].sign = 0;
        }
      }
    }
    // arr = arr.filter(Boolean)
    if (mode == "mode2")
      arr = arr.filter((x) => {
        return x != "+" && x != "-" && x != "*" && x != "/";
      });
    else if (mode == "mode3") {
      let arr2 = [];
      for (let i = 0; i < arr.length; i += 2) arr2.push(arr[i] + arr[i + 1]);
      arr = arr2;
    }
    if (this.str[0] == "+" || this.str[0] == "*")
      this.str = this.str.substring(1);
    return arr;
  }
  substitute(position = 0, by = "") {
    this.str =
      this.str.substring(0, position) + by + this.str.substring(position + 1);
    this.strUpdated = true;
  }
  partitioning() {
    let dPart;
    let sPart;
    let re; // digit part and symbol part respectively
    // m = this.str.toString().matchAll(/([\d.-]*)\**([^\d.-]*)/g)  //"-6.5*a*b" ==> ['-6.5*a*b', '-6.5', 'a*b', index: 0, input: '-6.5*a*b', groups: undefined]
    dPart = this.str.match(/^[\d.()\-]+/g);
    sPart = this.str.match(/[^\d.*\-][^\*\-]*/g);
    if (dPart == null) dPart = "1";
    else if (dPart == "-") dPart = -1;
    else dPart = dPart[0];
    if (sPart == null) sPart = "";
    else sPart = sPart.join("*");
    return [dPart, sPart];
  }
  _numden() {
    this.strUpdated = true;
    let fraction = this.splitIntoArrayByFree("/", "mode2");
    for (let i of fraction) {
      i._delOuterParen();
      if (i.hasFree("+-/")) i._addOuterParen();
    }
    this.numerator = fraction[0].splitIntoArrayByFree("*", "mode2");
    if (fraction.length > 1)
      this.denominator = fraction[1].splitIntoArrayByFree("*", "mode2");
  }
  _genStr() {
    //generate string from its numerator and denominator
    let tmp;
    let result = "";
    if (this.numerator.length > 0 || this.denominator.length > 0) {
      if (this.numerator.length > 0) result = this.numerator.join("*");
      else result == "1"; //:  such as []/[a,b]=> 1/(a*b)
      if (this.denominator.length > 0) {
        tmp = new CalcString(this.denominator.join("*"));
        if (this.denominator.length > 1) tmp._addOuterParen();
        result = result + "/" + tmp.str;
      }
    }
    return result;
  }
  _delOuterParen() {
    if (this.str[0] == "(" && this.str[this.str.length - 1] == ")")
      if (this.findFreeNdx("+-*/").length == 0) {
        this.str = this.str.substring(1, this.str.length - 1);
        this.strUpdated = true;
        return true;
      }
    return false;
  }
  _addOuterParen() {
    this.str = "(" + this.str + ")";
    this.strUpdated = true;
  }
  _opposite() {
    //a=>-a; -a=>a; a+b=>-a-b; -a-b=>a+b; -a*d-b*c=>a*d+b*c; -(a+b)=>(a+b);  (-a+b)=>(a-b); -(-a+b)/(-c+d)=>(-a+b)/(-c+d);  (-a+b)/(-c+d)=>(a-b)/(-c+d)
    // let result = new CalcString(this.str);
    // if (result.str[0] == "-") result.str = result.str.substring(1);
    // else {
    //   let arr1 = result.splitIntoArrayByFree("*/", "mode1");
    //   let firstPart = arr1[0];
    //   let flag = firstPart._delOuterParen();
    //   let arr2 = firstPart.splitIntoArrayByFree("+-", "mode2");
    //   for (let i of arr2) i.sign = !i.sign;
    //   firstPart.str = arr2.toSignedString();
    //   if (flag) firstPart._addOuterParen();
    //   result.str = "";
    //   for (let i = 0; i < arr1.length; i++) {
    //     let tmp = arr1[i].str || arr1[i];
    //     result.str = result.str + tmp;
    //   }
    // }
    let result = new CalcString(this.str);
    let arr1;
    let arr2;
    let toRevert;
    if (result.hasFree("+-")) {
      //a=>-a; -a=>a; a+b=>-a-b; -a-b=>a+b; -a*d-b*c=>a*d+b*c; -(a+b)=>(a+b);
      arr1 = result.splitIntoArrayByFree("+-", "mode2");
      for (let i of arr1) i.sign = !i.sign;
      result.str = arr1.toSignedString();
    } else {
      // (-a+b)=>(a-b); -(-a+b)/(-c+d)=>(-a+b)/(-c+d);  (-a+b)/(-c+d)=>(a-b)/(-c+d)
      arr1 = result.splitIntoArrayByFree("*/", "mode1");
      toRevert = arr1[0];
      let flag = toRevert._delOuterParen();
      arr2 = toRevert.splitIntoArrayByFree("+-", "mode2");
      for (let i of arr2) i.sign = !i.sign;
      toRevert.str = arr2.toSignedString();
      if (flag) toRevert._addOuterParen();
      arr1[0] = toRevert;
      result.str = "";
      for (let i = 0; i < arr1.length; i++) {
        let tmp = arr1[i].str || arr1[i];
        result.str = result.str + tmp;
      }
    }
    result.strUpdated = true;
    return result;
  }
  _expand() {
    this._numden();
    this.numerator[0] = this.numerator
      .sort(mixedCompare)
      .reduce(this._expandAB);
    this.str = this.numerator[0].str;
    if (this.denominator.length > 0) {
      if (this.numerator.hasFree("+-")) this.numerator._addOuterParen();
      this.denominator = this.denominator.reduce(this._expandAB);
      if (this.denominator.hasFree("+-")) this.denominator._addOuterParen();
      this.str = this.str + "/" + this.denominator.str;
    }
    this.strUpdated = true;
    return this;
  }
  _expandAB(a, b) {
    a._delOuterParen();
    b._delOuterParen();
    let ar1 = a.splitIntoArrayByFree("+-", "mode2");
    let ar2 = b.splitIntoArrayByFree("+-", "mode2");
    let tmp;
    let result;
    let ar3 = [];
    let sign;
    for (let x of ar1) {
      [x.dPart, x.sPart] = x.partitioning();
      for (let y of ar2) {
        [y.dPart, y.sPart] = y.partitioning();
        tmp = new CalcString();
        tmp.dPart = x.dPart * y.dPart;
        if (x.sPart && y.sPart) tmp.sPart = [x.sPart, y.sPart].join("*");
        //x.sPart=="" or y.sPart==""
        else tmp.sPart = x.sPart || y.sPart;
        if (tmp.sPart)
          if (tmp.dPart == 1) tmp.str = tmp.sPart;
          else tmp.str = [tmp.dPart, tmp.sPart].join("*");
        else tmp.str = tmp.dPart;
        tmp.sign = x.sign == y.sign ? 1 : 0;
        ar3.push(tmp);
      }
    }
    result = new CalcString(ar3.toSignedString());
    return result;
  }
  _factor() {
    // 8*a*a*b- 4*a*a + 2*a*a*c => 2*a*a*(4*b-2+1*c); -6-6*x=>-6*(1+x)
    let eleArr = [];
    let comArr = [];
    let comSet = [];
    let ar = this.splitIntoArrayByFree("+-");
    for (let i = 1; i < ar.length; i += 2)
      eleArr.push(ar[i].splitIntoArrayByFree("*", "mode2").map((x) => x.str));
    for (let i = 0; i < eleArr.length; i++)
      for (let j = 0; j < eleArr[i].length; j++)
        if (!comSet.includes(eleArr[i][j])) comSet.push(eleArr[i][j]);
    comSet.sort(mixedCompare);
    for (let com of comSet) {
      while (eleArr.every((x) => x.includes(com))) {
        // 8*a*a*b- 4*a*a + a*a => a*a*[8*b-4+1]
        comArr.push(com);
        for (let i = 0; i < eleArr.length; i++) {
          eleArr[i].splice(eleArr[i].indexOf(com), 1);
          if (eleArr[i].length == 0) eleArr[i] = ["1"];
        } // a*a => 1 when a,a are common factor
      }
      while (eleArr.every((x) => x.hasCommon(com))) {
        // 6*a- 3*a + 9 => 3*[2*a-1*a+3];  not solved yet: 8-6*a => 2*(4-3*a)
        comArr.push(com);
        for (let j of eleArr) {
          y = j.hasCommon(com);
          if (y == com && j.length > 1) j.splice(j.indexOf(y), 1);
          else j[j.indexOf(y)] = y / com;
        }
      }
    }
    if (comArr.length > 0) {
      for (let i = 0; i < eleArr.length; i++) {
        eleArr[i] = new CalcString(eleArr[i].join("*"));
        if (ar[i * 2] == "-") eleArr[i].sign = 0;
      }
      this.str = eleArr.toSignedString();
      this._addOuterParen();
      this.str = [comArr.join("*"), this.str].sort(mixedCompare).join("*");
      this.strUpdated = true;
    }
  }
  _addsub(op, other) {
    let expanded = false;
    this._delOuterParen();
    other._delOuterParen();
    if (other.str[0] == "-") op = "";
    let result = new CalcString(this.str + op + other.str); //-2*(n+2)*(4-n)*6-3*(n-1)+2*(3-n) => -12*(n...)-3*n-3+6-2*n => 3-n
    let arr = result.splitIntoArrayByFree("+-", "mode2").sort(mixedCompare);
    for (let i = 0; i < arr.length; i++)
      if (arr[i].str.includes("(")) {
        arr[i]._expand();
        expanded = true;
      }
    if (expanded) {
      result.str = arr.toSignedString();
      result.strUpdated = true;
      arr = result.splitIntoArrayByFree("+-", "mode2").sort(mixedCompare);
    }
    if (arr.length > 1) {
      let itemDict = new countingDict();
      for (let i = 0; i < arr.length; i++) {
        let sign = arr[i].sign ? "+" : "-";
        let ele = arr[i].split(/^([\d\.]+)\*/); //  4*a - 2.5*a - b -> 1.5*a - b
        if (ele.length > 1) {
          let addValue = Number(sign + ele[1]);
          itemDict.incrementItem(ele[2], addValue);
        } else {
          let addValue = Number(sign + 1);
          itemDict.incrementItem(ele[0], addValue);
        }
      }
      if (Object.keys(itemDict) == 0) {
        result.str = "0";
        result.strUpdated = true;
        return result;
      }
      result.str = "";
      // let sortedItems = {}
      // Object.keys(itemDict).sort(mixedCompare).forEach(x => { sortedItems[x] = itemDict[x] })
      // for (let x in sortedItems) {
      // 	let y = sortedItems[x]
      let num = 0;
      for (let x in itemDict) {
        let y = itemDict[x];
        if (isNaN(x)) {
          if (y == 1) result.str += "+" + x;
          else if (y == -1) result.str += "-" + x;
          else if (y > 0) result.str += "+" + y + "*" + x;
          else if (y < 0) result.str += y + "*" + x;
        } else {
          num += y * x;
        }
      }
      if (num != 0) result.str = num + result.str;
      if (result.str[0] == "+") result.str = result.str.substring(1);
      if (result.hasFree("+-")) result._factor();
      return result;
    }
  }
  _muldiv(op, other) {
    let sign = 1;
    let cancelled = false;
    let result = new CalcString("");
    this._numden();
    other._numden();
    if (op == "*") {
      result.numerator = this.numerator.concat(other.numerator);
      result.denominator = this.denominator.concat(other.denominator);
    } else if (op == "/") {
      result.numerator = this.numerator.concat(other.denominator);
      result.denominator = this.denominator.concat(other.numerator);
    }
    if (result.numerator.length > 1)
      result.numerator = result.numerator.filter((x) => x.str != "1");
    if (result.denominator.length > 1)
      result.denominator = result.denominator.filter((x) => x.str != "1");
    cancelled = result._cancel();
    if (cancelled) result._delOuterParen();
    return result;
  }
  _cancel() {
    let cancelled = false;
    let y;
    let sign = 1;
    let upper = new countingDict();
    let lower = new countingDict();
    for (let i of this.numerator) {
      if (i.str[0] == "-") {
        sign = !sign;
        i.str = i.str.substring(1);
      }
      upper.incrementItem(i.str);
    }
    for (let i of this.denominator) {
      if (i.str[0] == "-") {
        sign = !sign;
        i.str = i.str.substring(1);
      }
      lower.incrementItem(i.str);
    }
    for (let x in upper) {
      while (x in lower) {
        upper.decrementItem(x);
        lower.decrementItem(x);
        cancelled = true;
      }
      if (!cancelled) {
        y = new CalcString(x);
        y = y._opposite();
        while (y.str in lower) {
          upper.decrementItem(x);
          lower.decrementItem(y.str);
          sign = !sign;
          cancelled = true;
        }
      }
    }
    if (cancelled) {
      this.numerator = [];
      this.denominator = [];
      for (let i in upper)
        for (let j = 0; j < upper[i]; j++)
          this.numerator.push(new CalcString(i));
      for (let i in lower)
        for (let j = 0; j < lower[i]; j++)
          this.denominator.push(new CalcString(i));
      this.str = this._genStr();
      if (this.str == "")
        //if everything is cancelled
        this.str = "1";
      if (sign == 0) this.str = this._opposite().str;
      this.strUpdated = true;
    }
    return cancelled;
  }
  _simpleCaseProcess(op, other) {
    let [x, y] = [this.str, other.str];
    if (op == "*") {
      if (x == "0" || y == "0") return 0;
      if (x == "1") return other;
      if (x == "-1") return other._opposite();
      if (y == "1") return this;
      if (y == "-1") return this._opposite();
      if (!isNaN(x) && !isNaN(y)) return new CalcString(x * y);
      if (!this.hasFree("+-/") && !other.hasFree("+-/")) {
        //2*-a*b -> -2*a*b
        if (this.str.startsWith("-")) {
          this.sign = 0;
          this.str = this.str.substring(1);
        }
        if (other.str.startsWith("-")) {
          other.sign = 0;
          other.str = other.str.substring(1);
        }
        let result = new CalcString(this.str + "*" + other.str);
        if (this.hasFree("*") || other.hasFree("*")) {
          //3*a*2 -> 6*a
          result._numden();
          result.numerator.sort(mixedCompare);
          result = result.numerator.reduce((x, y) => {
            [x, y] = [x.toString(), y.toString()];
            if (!isNaN(x) && !isNaN(y)) return new CalcString(x * y);
            else return new CalcString(x + "*" + y);
          });
        }
        if (this.sign != other.sign) {
          result.sign = 0;
          result.str = "-" + result.str;
          result.strUpdated = true;
        }
        return result;
      }
    } else if (op == "/") {
      if (x == "0") return 0;
      if (y == "0") return new CalcString(x + "/" + "0");
      if (y == "1") return this;
      if (y == "-1") return this._opposite();
      if (x == y) return 1;
      if (x == "-" + y || y == "-" + x) return -1;
      if (!isNaN(x) && !isNaN(y)) return new CalcString(x / y);
      // if (!/[+-\/\*()]/.test(x) && !/[+-\/\*()]/.test(y))
      if (!this.hasFree("+-*/") && !other.hasFree("+-*/")) {
        if (y.startsWith("-")) {
          y = y.substring(1);
          if (x.startsWith("-")) x = x.substring(1);
          else x = "-" + x;
        }
        return new CalcString(x + "/" + y);
      }
    } else if (op == "+") {
      if (x == "0") return other;
      if (y == "0") return this;
      if (!/[+-\/\*()]/.test(x) && !/[+-\/\*()]/.test(y)) {
        [x, y] = [x, y].sort(mixedCompare);
        return new CalcString(x + "+" + y);
      }
    } else if (op == "-") {
      if (x == "0") return other._opposite();
      if (y == "0") return this;
      if (x == y) return 0;
      if (!/[+-\/\*()]/.test(x) && !/[+-\/\*()]/.test(y)) {
        if (x < y) return new CalcString(x + "-" + y);
        if (x > y) return new CalcString("-" + y + "+" + x);
      }
    }
    return false;
  }
  strOp(op, other) {
    let result = this._simpleCaseProcess(op, other);
    if (result !== false) return result;
    result = new CalcString("");
    if (op == "+" || op == "-") {
      let s1;
      let s2;
      if (op == "-") {
        other = other._opposite();
        op = "+";
      }
      //common denominator if possible:   d - a*b/c -> (d*c - a*b)/c
      this._numden();
      other._numden();
      let commonDenominator = [
        ...new Set(this.denominator.concat(other.denominator)).keys(),
      ];
      if (commonDenominator.length) {
        for (let x of commonDenominator) {
          if (!this.denominator.includes(x)) {
            this.numerator.push(x);
            this.needReduce = true;
          }
          if (!other.denominator.includes(x)) {
            other.numerator.push(x);
            other.needReduce = true;
          }
        }
        if (this.needReduce)
          this.numerator = [this.numerator.reduce((x, y) => x.strOp("*", y))];
        if (other.needReduce)
          other.numerator = [other.numerator.reduce((x, y) => x.strOp("*", y))];
      }
      this.numerator = new CalcString(this.numerator.join("*"));
      other.numerator = new CalcString(other.numerator.join("*"));
      s1 = this.numerator._addsub(op, other.numerator); // upper part
      if (commonDenominator.length > 0) {
        s2 = new CalcString(commonDenominator.join("*")); //lower part
        if (s1.hasFree("+-")) s1._addOuterParen();
        if (commonDenominator.length > 1) s2._addOuterParen();
        result = s1.strOp("/", s2);
      } else result = s1;
    } else if (op == "/" || op == "*") {
      if (this.hasFree("+-")) this._addOuterParen();
      if (other.hasFree("+-")) other._addOuterParen();
      this._numden();
      other._numden();
      if (op == "*") {
        result.numerator = this.numerator
          .concat(other.numerator)
          .sort(mixedCompare);
        result.denominator = this.denominator
          .concat(other.denominator)
          .sort(mixedCompare);
      } else if (op == "/") {
        result.numerator = this.numerator
          .concat(other.denominator)
          .sort(mixedCompare);
        result.denominator = this.denominator
          .concat(other.numerator)
          .sort(mixedCompare);
      }
      result.numerator = [result.numerator.reduce((x, y) => x.strOp("*", y))];
      if (result.denominator.length > 0)
        result.denominator = [
          result.denominator.reduce((x, y) => x.strOp("*", y)),
        ];
      result.str = result._genStr();
      result._numden();
      if (result._cancel()) result._delOuterParen();
      // result.str = math.simplify(result.str).toString();
      // result.strUpdated = true;
    }
    return result;
  }

  strOp1(op, other) {
    this._addOuterParen();
    other._addOuterParen();
    let result = new CalcString(
      math.simplify(this.str + op + other.str).toString()
    );
    return result;
  }
} //end of class

function mixedCompare(a, b) {
  // return 1 when exchange a and b; -1 when not change.
  let [aIsNum, bIsNum] = [!isNaN(a.toString()), !isNaN(b.toString())];
  if (aIsNum && bIsNum) return a - b;
  if (aIsNum) return -1;
  if (bIsNum) return 1;
  if (
    (!(a.startsWith("(") || a.startsWith("-(")) &&
      !(b.startsWith("(") || b.startsWith("-("))) || //: x, y
    ((a.startsWith("(") || a.startsWith("-(")) &&
      (b.startsWith("(") || b.startsWith("-(")))
  )
    //: (1-x) , -(1-x)
    return a.localeCompare(b, "en", { numeric: true });
  if (a.startsWith("(")) return 1;
  return -1;
}

Array.prototype.findMaxNdx = function () {
  let m;
  let ndx = 0;
  if (this.length > 0) {
    m = this[0];
    for (let i = 0; i < this.length; i++)
      if (this[i] > m) {
        m = this[i];
        ndx = i;
      }
    return ndx;
  }
};
Array.prototype.toSignedString = function () {
  let str = "";
  let sign;
  for (let i = 0; i < this.length; i++) {
    sign = this[i].sign ? "+" : "-";
    if (!this[i].sign && this[i].hasFree("+-")) {
      this[i] = this[i]._opposite();
      if (this[i].str[0] != "-") this[i].str = "+" + this[i].str;
    } else this[i].str = sign + this[i].str;
  }
  str = this.join("");
  if (str[0] == "+") str = str.substring(1);
  str = str.replaceAll("+-", "-");
  return str;
};
Array.prototype.hasCommon = function (x) {
  //return true if x is divisible by any of the elements in array
  for (y of this)
    if (!isNaN(x) && !isNaN(y) && x != 1 && y != 0 && y % x == 0) return y;
  return false;
};
Number.prototype.strOp = function (op, other) {
  let x = new CalcString(this.toString());
  return x.strOp(op, other);
};
//this.str "(-8-2*n+n*n)*(-14+4*n+n*n)"
// other.str "(1-n)"
